// 时间复杂度 O(n^2)
// 空间复杂度 O(1)

const { LinkedList } = require('../1. 链表基础/1. 建立线性链表')

function bubbleSort(head) {
    let i = head // 外循环次数
    let tail = null
    while (i) {
        let j = head
        while (j && j.next !== tail) {
            if (j.val > j.next.val) {
                // 交换两个节点的值
                [j.val, j.next.val] = [j.next.val, j.val ]
            }
            j = j.next
        }
        tail = j
        i = i.next
    }
    return head
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
bubbleSort(linkList.head)
console.log(linkList);